/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
	// 位数和，用来获取每个位置上的数的和
	const getBitSum = (num) => {
		let res = 0;
		while (num) {
			// 从最低位开始取
			res += num % 10;
			// 消除最低位
			num = Math.floor(num / 10);
		}
		return res;
	}

	// 1. 建立方向数组和最终的格子结果
	const directionArr = [
		[-1, 0],	// 上
		[1, 0],		// 下
		[0, -1],	// 左
		[0, 1]		//右
	];
	let set = new Set(['0, 0']);
	// 2. 维护一个队列表示当前所在的格子以及即将要遍历的格子
	let queue = [[0, 0]];
	// 3. 遍历这个队列
	while (queue.length) {
		let [x, y] = queue.shift();
		// 3.1. 在队列中遍历四个方向
		for (let i = 0; i < 4; i++) {
			let offsetX = x + directionArr[i][0];
			let offsetY = y + directionArr[i][1];
			// 超出条件
			if (offsetX < 0 || offsetX >= m || offsetY < 0 || offsetY >= n || getBitSum(offsetX) + getBitSum(offsetY) > k || set.has(`${offsetX}, ${offsetY}`)) {
				continue;
			}
			// 3.2. 符合条件的放入队列中准备下一次遍历
			queue.push([offsetX, offsetY]);
			// 3.3. 符合条件的加入最终的格子结果
			set.add(`${offsetX}, ${offsetY}`);			
		}
	}	
	// 4. 集合去重,返回格子数量
	return set.size;
};
console.log(movingCount(1,2,1))